package com.samxcode.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;


public class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;


    TreeNode(int x) {
        val = x;
    }


    public List<Integer> preorderTraversalIterative(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (root != null) {
            stack.add(root);
        }
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) {
                stack.add(node.right);
            }
            if (node.left != null) {
                stack.add(node.left);
            }
        }
        return result;
    }


    // non-recusive
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode curNode = root;
        TreeNode preNode = null;
        while (curNode != null || !stack.isEmpty()) {
            // add all left child node belong to this node into stack
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.peek();
            // if the right child of this node is null or has been visited, then visit the node
            if (curNode.right == null || curNode.right == preNode) {
                result.add(curNode.val);
                stack.pop();
                preNode = curNode;
                curNode = null;
            } else {
                curNode = curNode.right;
            }
        }
        return result;
    }

    //similar to double stack method, 
    //the result of the postorder traversal is the reversed result of preorder traversal with all tree's left and right child exchanged
    public List<Integer> postorderTravesl2(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<Integer>();
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        TreeNode node = root;
        while (node != null) {
            result.addFirst(node.val);
            if (node.left != null) {
                stack.addLast(node.left);
            }
            node = node.right;
            if (node == null && !stack.isEmpty()) {
                node = stack.pollLast();
            }
        }
        return result;
    }
}
